/**************************************************************************
 * @name: BinaryTree.c
 * @brief: 这是二叉树的代码
 * @date:
 * @author: boluzs@163.com
 * @note: None
 * @version: 1.0.0
 * @Copyright (c) 2024 by boluzs@163.com, All Rights Reserved.
 **************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

// 使用面向对象的思想构造二叉树中结点，双向链表结点分为3部分：键值+lchild指针域+rchild指针域
typedef int DataType_t; // 用于说明循环队列数据元素的类型 提高程序的可移植性

typedef struct TreeNode
{
    DataType_t Key;          // 键值，用于记录结点的数据
    struct TreeNode *Lchild; // 左子树，指向左子树的地址
    struct TreeNode *Rchild; // 右子树，指向左子树的地址
} Tnode_t, *Tnode_p;

/**************************************************************************
 * @name: BinaryTree_Create
 * @brief: 创建二叉树的根节点
 * @param {DataType_t} Data
 * @note: None
 * @retval: 函数调用成功，返回Tnode_p类型指针
 **************************************************************************/
Tnode_p BinaryTree_Create(DataType_t Data)
{
    // 1.为根结点申请堆内存，并进行错误处理
    Tnode_p Pmanager = (Tnode_p)calloc(1, sizeof(Tnode_p));
    if (NULL == Pmanager)
    {
        fprintf(stderr, "Calloc For Node Error,errno=%d,%s\n", errno, strerror(errno));
        exit(-1);
    }

    // 2.初始化头结点指针域（数据域是空闲的）
    Pmanager->Lchild = NULL;
    Pmanager->Rchild = NULL;
    printf("Create CircularDoubleLinkedList Successfully!\n");
    return Pmanager;
}

/**
 * @name: BinaryTree_NewNode
 * @brief: 创建新结点
 * @param {DataType_t} Data：待创建的结点键值数据
 * @note: None
 * @retval: 函数调用成功，返回Tnode_p类型指针
 */
Tnode_p BinaryTree_NewNode(DataType_t Data)
{
    // 1.为新结点申请堆内存，并进行错误处理
    Tnode_p NewNode = (Tnode_p)calloc(1, sizeof(Tnode_p));
    if (NULL == NewNode)
    {
        fprintf(stderr, "Calloc For Node Error,errno=%d,%s\n", errno, strerror(errno));
        exit(-1);
    }
    // 2.初始化新结点
    NewNode->Key = Data;
    NewNode->Lchild = NULL;
    NewNode->Rchild = NULL;
    printf("Create NewNode Successfully!\n");
    return NewNode;
}

/**************************************************************************
 * @name: BinaryTree_Count
 * @brief: 需要计算一颗二叉树的结点数量
 * @param {Tnode_p} Root
 * @note: None
 * @retval: None
 **************************************************************************/
int BinaryTree_Count(Tnode_p Root)
{
    int sum = 1;
    // 判断是否有左子树
    if (Root->Lchild != NULL)
    {
        sum += BinaryTree_Count(Root->Lchild);
    }
    // 判断是否有右子树
    if (Root->Rchild != NULL)
    {
        sum += BinaryTree_Count(Root->Rchild);
    }

    return sum;
}

/**************************************************************************
 * @name: Teacher_BinaryTree_GetNodeCount
 * @brief: 需要计算一颗二叉树的结点数量(老师的代码)
 * @param {Tnode_p} Root
 * @note: 计算左子树的结点数量 + 计算右子树的结点数量 + 1（根结点）
 * @retval: None
 **************************************************************************/
int Teacher_BinaryTree_GetNodeCount(Tnode_p Root)
{
    int lchild_cnt = 0; // 用于记录左子树的结点数量
    int rchild_cnt = 0; // 用于记录右子树的结点数量

    if (NULL == Root)
    {
        return 0;
    }
    else
    {
        // 计算左子树的结点数量
        lchild_cnt = Teacher_BinaryTree_GetNodeCount(Root->Lchild);
        // 计算右子树的结点数量
        rchild_cnt = Teacher_BinaryTree_GetNodeCount(Root->Rchild);
        // 返回所有结点的数量
        return lchild_cnt + rchild_cnt + 1;
    }
}

/**************************************************************************
 * @name: BinaryTree_CountTreeNode0
 * @brief: 需要计算一颗二叉树的叶子结点数量
 * @param {Tnode_p} Root
 * @note: 计算度为0的结点数量
 * @retval: None
 **************************************************************************/
int BinaryTree_CountTreeNode0(Tnode_p Root)
{
    int lchild_cnt = 0; // 用于记录左子树的结点数量
    int rchild_cnt = 0; // 用于记录右子树的结点数量

    if (NULL == Root)
    {
        return 0;
    }
    else if (NULL == Root->Lchild && NULL == Root->Rchild)
    {
        return 1;
    }
    else
    {
        // 计算左子树的结点数量
        lchild_cnt = BinaryTree_CountTreeNode0(Root->Lchild);
        // 计算右子树的结点数量
        rchild_cnt = BinaryTree_CountTreeNode0(Root->Rchild);
        // 返回所有叶子结点的数量
        return lchild_cnt + rchild_cnt;
    }
}

/**************************************************************************
 * @name: BinaryTree_CountHeight
 * @brief: 计算一棵树的深度
 * @param {Tnode_p} Root
 * @note: None
 * @retval: None
 **************************************************************************/
int BinaryTree_GetDepth(Tnode_p Root)
{
    int ltree_depth = 0; // 用于记录左子树的深度
    int rtree_depth = 0; // 用于记录右子树的深度

    if (NULL == Root)
    {
        return 0;
    }
    else
    {
        // 计算左子树的结点数量
        ltree_depth = BinaryTree_GetDepth(Root->Lchild);
        // 计算右子树的结点数量
        rtree_depth = BinaryTree_GetDepth(Root->Rchild);
        // 返回深度更高的子树+1
        return (ltree_depth > rtree_depth ? ltree_depth  : rtree_depth) + 1;
    }
}

int main(int argc, char const *argv[])
{
    Tnode_p Root = BinaryTree_Create(1);
    Root->Lchild = BinaryTree_NewNode(2);
    Root->Rchild = BinaryTree_NewNode(3);
    Root->Lchild->Lchild = BinaryTree_NewNode(4);
    Root->Lchild->Rchild = BinaryTree_NewNode(5);
    Root->Rchild->Lchild = BinaryTree_NewNode(6);
    Root->Rchild->Rchild = BinaryTree_NewNode(7);
    Root->Rchild->Rchild->Rchild = BinaryTree_NewNode(8);
    printf("这棵树的总结点数：%d\n", BinaryTree_Count(Root));
    printf("这棵树的总结点数：%d\n", Teacher_BinaryTree_GetNodeCount(Root));
    printf("这棵树的叶子结点数：%d\n", BinaryTree_CountTreeNode0(Root));
    printf("这棵树的深度：%d\n", BinaryTree_GetDepth(Root));
    return 0;
}
